
//Definition for singly-linked list.
// struct ListNode {
//     int val;
//     struct ListNode *next;
// };

struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}


struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* n1, * n2, * n3;
    if (head == NULL)
        return NULL;

    n1 = NULL;
    n2 = head;
    n3 = n2->next;

    while (n2)
    {
        n2->next = n1;

        n1 = n2;
        n2 = n3;
        if (n3 != NULL)
            n3 = n3->next;
    }int kthToLast(struct ListNode* head, int k) {
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        while (--k)
        {
            fast = fast->next;
        }

        while (fast->next)
        {
            slow = slow->next;
            fast = fast->next;
        }

        return slow->val;
    }struct ListNode* head1 = list1;
    struct ListNode* head2 = list2;
    struct ListNode* newhead = NULL;
    struct ListNode* cur = newhead;
    while (head1 && head2) {
        if (head1->val < head2->val) {

            if (newhead == NULL) {
                newhead = head1;
            }
            else {
                cur->next = head1;
                cur = cur->next;
                head1 = head1->next;
            }
        }
        else {
            if (head1->val >= head2->val) {
                if (newhead == NULL) {
                    newhead = head2;
                }
                else {
                    cur->next = head2;
                    cur = cur->next;
                    head2 = head2->next;
                }
            }
        }
        if (list1 != NULL) {
            cur->next = head1;
        }
        else {
            cur->next = head2;
        }
        return newhead;
